package mathlib.expr {
	import mathlib.expr.datatype.TokenType;
	import mathlib.expr.datatype.ParseTree;

	/** 
	* Converts strings, ParseTrees, or Token arrays into usable CompiledFns.
	*/
	public class Compiler {
		/**
		* Compile a string into an evaluable CompiledFn.
		* @param env The Environment to use for lookups of functions, operators,
		*  constants, and variable names.
		* @param s The expression string to tokenize, parse, and compile.
		* @param optimize If true, the compiler will attempt to optimize the
		*  resulting CompiledFn for speed. At the moment, this just collapses
		*  constant subtrees of the ParseTree to a single number.
		* @throws SyntaxError <code>SyntaxError</code>: There was an error
		*  parsing the given string. The <code>message</code> member of the
		*  exception contains a human-readable hint at what went wrong.
		*/
		public static function compile(env:Environment, s:String, optimize:Boolean = true):CompiledFn {
			return compileTokenArray(env, Lexer.lex(env, s), optimize);
		}
		
		/**
		* Compile an array of Tokens (generated by the Lexer) into an evaluable
		* CompiledFn.
		* @param env The Environment to use for lookups of functions, operators,
		*  constants, and variable names.
		* @param tokens An array of Tokens representing the tokenized expression
		*  to compile. This may be generated by <code>Lexer.lex()</code>.
		* @param optimize If true, attempt to optimize the resulting CompiledFn.
		*  See the <code>compile</code> method for more details.
		* @throws SyntaxError <code>SyntaxError</code>: There was an error
		*  parsing the given string. The <code>message</code> member of the
		*  exception contains a human-readable hint at what went wrong.
		* @see Lexer#lex()
		* @see #compile()
		*/
		public static function compileTokenArray(env:Environment, tokens:Array, optimize:Boolean = true):CompiledFn {
			return compileParseTree(env, Parser.parse(tokens), optimize);
		}
		
		/**
		* Compile a ParseTree (generated by the Parser) into an evaluable
		* CompiledFn.
		* @param env The Environment to use for lookups of functions, operators,
		*  constants, and variable names.
		* @param pt The ParseTree representing the parsed expression to compile.
		*  This may be generated by <code>Parser.parse()</code>.
		* @param optimize If true, attempt to optimize the resulting CompiledFn.
		*  See the <code>compile</code> method for more details.
		* @see Parser#parse()
		* @see #compile()
		*/
		public static function compileParseTree(env:Environment, pt:ParseTree, optimize:Boolean = true):CompiledFn {
			var prefix:Array = new Array();

			if(optimize)
				optPtToArray(env, prefix, pt);
			else
				ptToArray(prefix, pt);

			return new CompiledFn(env, prefix);
		}
		
		/**
		* Performs an optimizing prefix traversal of the given ParseTree,
		* accumulating results in <code>arr</code>. It is "optimizing" in the
		* sense that constant subtrees are evaluated to their Number value.
		* @param env The Environment to use for lookups.
		* @param arr The values of the tokens in the ParseTree will be
		*  accumulated in this Array, in prefix order.
		* @param pt The ParseTree to traverse.
		*/
		private static function optPtToArray(env:Environment, arr:Array, pt:ParseTree):void {
			var child:ParseTree;
			var tempCFn:CompiledFn;
			var tempPrefix:Array;
			
			if(pt.isLeaf)
				arr.push(pt.token.val);
			
			else if(isConstantTree(pt)) {
				tempPrefix = new Array();
				
				// We call the non-optimizing version to naively traverse the
				// constant subtree and avoid an infinite regress.
				ptToArray(tempPrefix, pt);

				tempCFn = new CompiledFn(env, tempPrefix);
				
				// Since we are guaranteed there are no variables in this
				// subtree, we call evalAsIs, which doesn't make us give it
				// values for the variables.  The Number result is added to the
				// prefix array in place of the subtree.
				arr.push(tempCFn.evalAsIs());
			}
			
			else {
				arr.push(pt.token.val);
				for each(child in pt.children)
					optPtToArray(env, arr, child);
			}
		}
		
		
		/**
		* Performs a prefix traversal of the given ParseTree, accumulating
		* results in <code>arr</code>. This version makes no attempt to 
		* optimize constant subtrees, so it doesn't need to know about the
		* Environment.
		* @param arr The values of the tokens in the ParseTree will be
		*  accumulated in this Array, in prefix order.
		* @param pt The ParseTree to traverse.
		*/
		private static function ptToArray(arr:Array, pt:ParseTree):void {
			var child:ParseTree;
			
			arr.push(pt.token.val);

			if(!pt.isLeaf) {
				for each(child in pt.children)
					ptToArray(arr, child);
			}
		}
		
		/** Returns true if the given ParseTree contains no variables. */
		private static function isConstantTree(pt:ParseTree):Boolean {
			return pt.token.type != TokenType.VAR && 
			       (pt.isLeaf || areConstantTrees(pt.children));
		}
		
		/**
		* Returns true if the given array of ParseTrees contain no varaibles.
		* An empty array is considered constant.
		*/
		private static function areConstantTrees(pts:Array):Boolean {
			var pt:ParseTree;
			
			for each(pt in pts)
				if(!isConstantTree(pt)) return false;

			return true;
		}
	}
}
